1. Field of the Invention
The invention relates to a Very Large Scale Integration (VLSI) hardware structure. and more particular to a method and an apparatus for fast rotation, in which each rotation is performed by using only few shift-addition operation.
2. Description of the Related Art
Conventionally, the basic arithmetic of Digital Signal Processing (DSP) is a summation of multiplication performed by a multiplier. The arithmetic is called xe2x80x9cmultiplication-accumulation arithmeticxe2x80x9d. The disadvantages of this arithmetic are: 1) a large word width of resultant data is needed to guarantee the accuracy because of numerical sensitivity: and 2) a problem in system stability or robustness is caused, so that more digits are reserved for calculation. The consequence of the above two disadvantages are that the additional consumption of hardware for internal bus and storage.
Orthogonal Transform (OT) is an important content of DSP and has been broadly applied in data compression and analysis. It has been proved in mathematics that a very good robustness is obtained by employing Givens rotation sequence to perform OT. Givens rotation is a unit matrix based on planar rotation. Assuming that Gn(k, l, xcex8) is a Givens rotation, and             G      n        ⁡          (              k        ,        l        ,        θ            )        =                    [                                                            I                                  k                  -                  1                                                                                    xe2x80x83                                                                    xe2x80x83                                                                    xe2x80x83                                                                    xe2x80x83                                                                                        xe2x80x83                                                                    cos                ⁢                                  xe2x80x83                                ⁢                θ                                                                    xe2x80x83                                                                                      -                  sin                                ⁢                                  xe2x80x83                                ⁢                θ                                                                    xe2x80x83                                                                                        xe2x80x83                                                                    xe2x80x83                                                                    I                                  l                  -                  k                  -                  1                                                                                    xe2x80x83                                                                    xe2x80x83                                                                                        xe2x80x83                                                                    sin                ⁢                                  xe2x80x83                                ⁢                θ                                                                    xe2x80x83                                                                    cos                ⁢                                  xe2x80x83                                ⁢                θ                                                                    xe2x80x83                                                                                        xe2x80x83                                                                    xe2x80x83                                                                    xe2x80x83                                                                    xe2x80x83                                                                    I                                  n                  -                  1                                                                    ]            ⁢              xe2x80x83            ⁢              "LeftBracketingBar"        θ        "RightBracketingBar"              ≤    π  
wherein (k, l) represents rotation for kth and lth columns and rows. The rotation is an orthogonal matrix, so that value of the rotation matrix or the vector is kept constant before and after rotation.
To perform the above Givens rotation, Cordic algorithm is conventionally adopted. In Cordic algorithm, simple xe2x80x9cright shift-addition and subtractionxe2x80x9d calculation is used for planar rotation with infinitesimal angle. Through reiteratively calculation such as multiplication, division, trigonometry, and hyperbolic functions, Cordic algorithm has been broadly applied in palmar calculators. However, since Cordic algorithm is much more complex than xe2x80x9cmultiplication-accumulation arithmeticxe2x80x9d, this kind of rotation arithmetic cannot be performed in OT for further application.
To solve the above problem, A. Lightenberg, et. al. have developed an image processing chip in which Givens rotator is adapted to perform a two-dimensional 8xc3x978 discrete cosine transform (DCT). Yet, four multipliers are used to calculation the rotation.
It is therefore an object of the invention to provide a method and an apparatus for fast rotation for fast realization of Givens rotation. A fast rotator is developed in which each rotation with an arbitrary angle is performed by only one or few times of xe2x80x9cshift-additionxe2x80x9d. The fast rotator can be cascaded in pipelines for high throughput. This fast rotator can be used as the arithmetic core for the new VLSI-DSP to perform various OT by Givens rotation sequences. Therefore, a very good robustness is obtained, and furthermore, the computing complexity for the fast rotator is comparable to the conventional xe2x80x9cmultiplication-accumulation arithmeticxe2x80x9d. By employing the fast rotator according to the invention as a computing kernel in digital image processing, especially in high definition television (HDTV) images and high resolution medical X-ray images, the total amount of image data can be transformed and reduced to an acceptable amount.
To achieve these objects and advantages, and in accordance with the purpose of to the invention, as embodied and broadly described herein, the invention is directed towards an apparatus of fast rotation, including, a plurality of pipelines. Each of the pipelines comprises: a plurality of multiplexes, for data filtering and selecting; a plurality of shifters, to perform fast rotation of data selected by the multiplexes; and a plurality of adders/subtractors, to complete computation after the fast rotation and to obtain a resultant data.
To achieve these objects and advantages, and in accordance with the purpose of the invention, as embodied and broadly described herein, the invention is directed toward a method of fast rotation. A pipeline comprising a plurality of multiplexes, a plurality of shifters, to perform fast rotation of data selected by the multiplexes, and a plurality of adders/subtractors is provided. A plurality sets of data is input to be filtered and selected by the multiplexes. Fast rotation is performed to the data selected by the multiplexes. A final computation is performed a set of resultant data is output through the adder/subtractors.
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed.